package tree;

import java.util.Stack;

/**
 * 700. 二叉搜索树中的搜索
 * 二叉搜索树的特性：左叶子的最大值小于根节点，根节点大于右叶子节点的最小值（有序性）
 *
 * @author Api
 * @date 2023/10/25 0:57
 */
public class Code700_SearchInBinarySearchTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 递归,利用二叉搜索树的特性
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        TreeNode result = null; // 记录指针
        if (root.val > val) {
            result = searchBST(root.left, val);
        }
        if (root.val < val) {
            result = searchBST(root.right, val);
        }
        return result;
    }
    // 递归，普通二叉树
    public TreeNode searchBST1(TreeNode root, int val){
        if (root == null || root.val == val){
            return root;
        }
        TreeNode left = searchBST1(root.left, val);
        if (left != null){
            return left;
        }
        return searchBST1(root.right, val);
    }

    // 迭代，普通二叉树
    public TreeNode searchBST2(TreeNode root, int val){
        if (root == null || root.val == val){
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.val == val){
                return node;
            }
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return null;
    }

    // 迭代，利用二叉搜索树特点，优化，可以不需要栈
    public TreeNode searchBST3(TreeNode root, int val){
        while(root != null){
            if (val < root.val){
                root = root.left;
            } else if (val > root.val) {
                root = root.right;
            }else{
                return root;
            }
        }
        return null;
    }
}
